package com.datastructure.test.levelorderbottom;

import java.util.ArrayList;

public class LevelOrderBottom {

    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {

    }

    public int[][] levelOrderBottom (TreeNode root) {
        // write code here
        int[][] result = null;
        ArrayList<Integer> list = null;
        int[] data = null;
        iterator(root,0);
        int size = res.size();
        result=new int[size][];
        for (int i = size -1; i >= 0; i--) {
            list = res.get(i);
            int length = list.size();
            data = new int[length];
            for (int j = 0; j < length; j++) {
                data[j]= list.get(j);
            }
            result[size-i-1]=data;
        }
        return result;
    }

    private void iterator(TreeNode root,int level) {
        if(res.size()==level){
            res.add(new ArrayList<>());
        }
        ArrayList<Integer> list = res.get(level);
        list.add(root.val);
        if(root.left!=null){
            iterator(root.left,level+1);
        }
        if(root.right!=null){
            iterator(root.right,level+1);
        }
    }
}

class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
   public TreeNode(int val) {
     this.val = val;
   }
 }
